package Top_Interview_Questions.Math;

/**
 * @Author: 吕庆龙
 * @Date: 2020/3/11 20:34
 * <p>
 * 还有一个牛顿迭代法
 */
public class _0069 {

    public static void main(String[] args) {
        _0069 test = new _0069();
        test.mySqrt(9);
    }

    /**
     * 牛顿迭代法
     */
    public int mySqrt(int a) {
        long x = a;
        while (x * x > a) {
            x = (x + a / x) / 2;
        }
        return (int) x;
    }




    /**
     * 干脆我不讨论 a 的边界，让二分法去排除不符合的区间吧，对数级别的时间复杂度对性能不会有很大影响。
     */
    public int mySqrt3(int x) {
        long left = 0;
        long right = Integer.MAX_VALUE;
        while (left < right) {
            // 这种取中位数的方法又快又好，是我刚学会的，原因在下面这篇文章的评论区
            // https://www.liwei.party/2019/06/17/leetcode-solution-new/search-insert-position/
            // 注意：这里得用无符号右移
            long mid = (left + right + 1) >>> 1;
            long square = mid * mid;
            if (square > x) {
                right = mid - 1;
            } else {
                left = mid;
            }
        }
        return (int) left;
    }




    public int mySqrt2(int x) {
        if (x == 0) {
            return 0;
        }
        // 注意：针对特殊测试用例，例如 2147395599
        // 要把搜索的范围设置成长整型
        long left = 1;
        long right = x / 2;
        while (left < right) {
            // 注意：这里一定取右中位数，如果取左中位数，代码会进入死循环
            // long mid = left + (right - left + 1) / 2;
            long mid = (left + right +1) >>> 1;
            long square = mid * mid;
            if (square > x) {
                right = mid - 1;
            } else {
                left = mid;
            }
        }
        // 因为一定存在，因此无需后处理
        return (int) left;
    }

    /**
     * 左中位数版本，方便统一记忆，我都是用左中位数的，怕弄混了～
     * 评论区: hongyi
     */
    public int mySqrt1(int x) {
        long tmp_x = x; // 为了后面做比较的时候类型一致
        long i = 0;
        long j = x;
        while(i < j){
            long mid = (i + j) >>> 1; // 这里用左中位数
            if(mid * mid < tmp_x){
                i = mid + 1;
                if(i * i > tmp_x) return (int)mid; //因为用了左边界，所以要多一次夹逼
            }else{
                j = mid;
            }
        }
        return (int)i;
    }

}
